UVa/12316 - Sewing Buttons with Grandma/Main2.java

   1 // Accepted - runs in 1.172s
   2 import java.io.*;
   3 import java.util.*;
   4 import java.math.*;
   5
   6 public class Main2 {
   7
   8     public static void main(String[] args) throws FileNotFoundException {
   9         Scanner cin = new Scanner(System.in);
  10         //Scanner cin = new Scanner(new FileInputStream(new File("in.txt")));
  11         int m, k;
  12
  13         int MAXN = 55;
  14         BigInteger choose[][] = new BigInteger[MAXN][MAXN];
  15         choose[0][0] = BigInteger.ONE;
  16         for (int i = 0; i < MAXN; ++i) {
  17             for (int j = 0; j < MAXN; ++j) {
  18                 if (i != 0 || j != 0) choose[i][j] = BigInteger.ZERO;
  19                 if (i > 0) choose[i][j] = choose[i][j].add(choose[i-1][j]);
  20                 if (i > 0 && j > 0) choose[i][j] = choose[i][j].add(choose[i-1][j-1]);
  21             }
  22         }
  23
  24         while (true) {
  25             m = cin.nextInt();
  26             k = cin.nextInt();
  27             if (m == 0 && k == 0) break;
  28
  29             int avail[] = new int[k];
  30             for (int i = 0; i < k; ++i) {
  31                 avail[i] = cin.nextInt();
  32             }
  33
  34             BigInteger dp[][] = new BigInteger[k+1][m+1];
  35             for (int b = 1; b <= m; ++b) {
  36                dp[k][b] = BigInteger.ZERO;
  37             }
  38             dp[k][0] = BigInteger.ONE;
  39
  40             for (int i = k - 1; i >= 0; --i) {
  41                 for (int b = 0; b <= m; ++b) {
  42                     dp[i][b] = dp[i+1][b];
  43                     for (int n = 1; n <= avail[i] && b - n >= 0; n++) {
  44                           dp[i][b] = dp[i][b].add(dp[i+1][b-n].multiply(choose[b][n]));
  45                     }
  46                 }
  47             }
  48             System.out.println(dp[0][m]);
  49         }
  50     }
  51
  52 }